题解
二叉树后序遍历的应用,每个结点遍历一次,时间复杂度O(n)
,空间复杂度O(1)
代码
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func pruneTree(root *TreeNode) *TreeNode {
rootSum := prune(root)
if rootSum == 0{
return nil
}
return root
}
func prune(root *TreeNode) int {
sum := (*root).Val
if (*root).Left != nil{
val := prune((*root).Left)
if val == 0{
(*root).Left = nil
}else{
sum += val
}
}
if (*root).Right != nil{
val := prune((*root).Right)
if val == 0{
(*root).Right = nil
}else{
sum += val
}
}
return sum
}
留言